- Title
- Equality of domination and transversal numbers in hypergraphs
- Creator
- Arumugam, S.; Jose, Bibin K.; Bujtás, Csilla; Tuza, Zsolt
- Relation
- Discrete Applied Mathematics Vol. 161, Issue 13-14, p. 1859-1867
- Publisher Link
- http://dx.doi.org/10.1016/j.dam.2013.02.009
- Publisher
- Elsevier BV
- Resource Type
- journal article
- Date
- 2013
- Description
- A subset S of the vertex set of a hypergraph ℋ is called a dominating set of ℋ if for every vertex v not in S there exists u ∈ S such that u and v are contained in an edge in ℋ. The minimum cardinality of a dominating set in ℋ is called the domination number of ℋ and is denoted by γ(ℋ). A transversal of a hypergraph ℋ is defined to be a subset T of the vertex set such that T ⋂ E ≠ Ø for every edge E of ℋ. The transversal number of ℋ, denoted by t.(ℋ), is the minimum number of vertices in a transversal. A hypergraph is of rank k if each of its edges contains at most k vertices. The inequality t(ℋ) = γ(ℋ) is valid for every hypergraph ℋ without isolated vertices. In this paper, we investigate the hypergraphs satisfying t(ℋ) = γ(ℋ), and prove that their recognition problem is NP-hard already on the class of linear hypergraphs of rank 3, while on unrestricted problem instances it lies inside the complexity class ϴ p2. Structurally we focus our attention on hypergraphs in which each subhypergraph ℋ¹ without isolated vertices fulfills the equality t(ℋ¹) = (ℋ¹). We show that if each induced subhypergraph satisfies the equality then it holds for the non-induced ones as well. Moreover, we prove that for every positive integer k, there are only a finite number of forbidden subhypergraphs of rank k, and each of them has domination number at most k.
- Subject
- hypergraph; domination number; transversal number; hitting set; hereditary property; computational complexity; polynomial hierarchy
- Identifier
- http://hdl.handle.net/1959.13/1296936
- Identifier
- uon:19337
- Identifier
- ISSN:0166-218X
- Language
- eng
- Reviewed
- Hits: 2735
- Visitors: 2688
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|